containers.internal.node source code

1 /**
2  * Templates for container node types.
3  * Copyright: © 2015 Economic Modeling Specialists, Intl.
4  * Authors: Brian Schott
5  * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
6  */
7 module containers.internal.node;
8 
9 template FatNodeInfo(size_t bytesPerItem, size_t pointerCount, size_t cacheLineSize = 64,
10 	size_t extraSpace = size_t.max)
11 {
12 	import std.meta : AliasSeq;
13 	import std.format : format;
14 	template fatNodeCapacity(alias L, bool CheckLength = true)
15 	{
16 		enum size_t optimistic = (cacheLineSize
17 			- ((void*).sizeof * pointerCount) - L) / bytesPerItem;
18 		static if (optimistic > 0)
19 		{
20 			enum fatNodeCapacity = optimistic;
21 			static if (CheckLength)
22 			{
23 				static assert(optimistic <= L * 8, ("%d bits required for bookkeeping"
24 					~ " but only %d are possible. Try reducing the cache line size argument.")
25 					.format(optimistic, L * 8));
26 			}
27 		}
28 		else
29 			enum fatNodeCapacity = 1;
30 	}
31 	static if (extraSpace == size_t.max)
32 	{
33 		static if (__traits(compiles, fatNodeCapacity!(ubyte.sizeof)))
34 			alias FatNodeInfo = AliasSeq!(fatNodeCapacity!(ubyte.sizeof), ubyte);
35 		else static if (__traits(compiles, fatNodeCapacity!(ushort.sizeof)))
36 			alias FatNodeInfo = AliasSeq!(fatNodeCapacity!(ushort.sizeof), ushort);
37 		else static if (__traits(compiles, fatNodeCapacity!(uint.sizeof)))
38 			alias FatNodeInfo = AliasSeq!(fatNodeCapacity!(uint.sizeof), uint);
39 		else static if (__traits(compiles, fatNodeCapacity!(ulong.sizeof)))
40 			alias FatNodeInfo = AliasSeq!(fatNodeCapacity!(ulong.sizeof), ulong);
41 		else static assert(false, "No type big enough to store " ~ extraSpace.stringof);
42 	}
43 	else
44 		alias FatNodeInfo = AliasSeq!(fatNodeCapacity!(extraSpace, false), void);
45 }
46 
47 // Double linked fat node of int with bookkeeping in a uint should be able to
48 // hold 11 ints per node.
49 // 64 - 16 - 4 = 4 * 11
50 version (X86_64)
51 	static assert (FatNodeInfo!(int.sizeof, 2)[0] == 11);
52 
53 template shouldNullSlot(T)
54 {
55 	import std.traits;
56 	enum shouldNullSlot = isPointer!T || is (T == class) || is (T == interface) || isDynamicArray!T 
57 							|| is(T == delegate); // closures or class method shoulde be null for GC recycle
58 }
59 
60 template shouldAddGCRange(T)
61 {
62 	import std.traits;
63 	enum shouldAddGCRange = hasIndirections!T;
64 }
65 
66 static assert (shouldAddGCRange!string);
67 static assert (!shouldAddGCRange!int);
68 
69 template fullBits(T, size_t n, size_t c = 0)
70 {
71 	static if (c >= (n - 1))
72 		enum T fullBits = (T(1) << c);
73 	else
74 		enum T fullBits = (T(1) << c) | fullBits!(T, n, c + 1);
75 }
76 
77 static assert (fullBits!(ushort, 1) == 1);
78 static assert (fullBits!(ushort, 2) == 3);
79 static assert (fullBits!(ushort, 3) == 7);
80 static assert (fullBits!(ushort, 4) == 15);